package code.starivan.leetcode;

import code.starivan.leetcode.common.ListNode;

/**
 * Created by Ivan on 2015/10/19.
 */
public class N234_PalindromeLinkedList {
    public static void test()
    {
        ListNode n1=new ListNode(1);
        ListNode n2=new ListNode(1);
        ListNode n3=new ListNode(3);
        ListNode n4=new ListNode(3);
        ListNode n5=new ListNode(2);
        ListNode n6=new ListNode(1);

        n1.next=n2;
      /*  n2.next=n3;
        n3.next=n4;
        n4.next=n5;
        n5.next=n6;*/
        System.out.print(new N234_PalindromeLinkedList().isPalindrome(n1));
    }


    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null){
            return true;
        }

        int length=0;
        ListNode node=head;
        while (node!=null){
            length++;
            node=node.next;
        }

        int k=length/2;
        ListNode mid=head;
        while (--k>0){
            mid=mid.next;
        }

        ListNode rev=reverse(mid.next);
        k=length/2;
        ListNode l=head;
        ListNode r=rev;
        boolean ret=true;
        while (k-->0){
            if(l.val!=r.val){
                ret=false;
                break;
            }

            l=l.next;
            r=r.next;
        }

        mid.next=reverse(rev);
        return ret;
    }

    private ListNode reverse(ListNode head){
        if(head==null){
            return null;
        }

        ListNode node=head;
        ListNode pre=null;
        while (node!=null){
            ListNode next=node.next;
            node.next=pre;
            pre=node;
            node=next;
        }

        return pre;
    }
}
